# 截木头
"""
题目描述：
给定一个数组nums，每个元素都代表一个木头的长度，
木头可以任意截断。从这堆木头中截出至少k个长度为 m 的木块。
已知k， 求m的最大值。

输入： k = 5, nums = [4, 7, 2, 10, 5]
输出：4
解释：
最多可以把数组分成5段长度为4的木头：4， 4 + 3， 2， 4 + 4 + 2， 4 + 1
可以看出有5个4。
"""

nums = [4, 7, 2, 10, 5]
k = 5

def cutWood(nums: list, k: int) -> int:
    """
        直接模拟，暴力破解。 从1米开始尝试
    """
    i = 1; 
    while True: 
        total = 0
        for num in nums:
            total += num // i

        if total < k: return i - 1
        else: i += 1



# 优化代码：
"""
上面的代码慢在了那里呢？ 只要是线性的遍历1，2,3，，n去试哪一个是需要的 m
既然是在升序的序列中，寻找一个合适的值， 那么就可以使用二分查找解决。
"""


def cutCount(nums: list, leg: int) -> int:
    """ 定义一个计算截取指定长度能砍多少段的函数 """
    total = 0
    for num in nums:
        total += num // leg
    return total

def cutWoodBinary(nums: list, k: int) -> int:
    """
        二分查找法解决
    """
    left, right = 1, 1000   # 假设数组最大长度为1000
    while left < right:
        mid = left + (right - left + 1) // 2
        if cutCount(nums, mid) >= k:
            left = mid
        else:
            right = mid - 1

    return left 

rst = cutWoodBinary(nums, k)
print(rst)

